n=800;
m=5000;
k=8000;
D=[68,67,58,1,90,50,36,21,69,21,54,47,8,87,41,45,43,78,15,95,59,45,96,66,85,78,56,26,48,49,90,80,80,48,87,92,40,16,21,44,76,6,100,28,92,28,85,16,11,84,86,29,37,77,23,16,66,37,44,97,84,7,100,38,40,51,32,1,1,9,50,42,1,26,11,39,87,39,1,49,75,92,89,77,30,15,86,33,54,98,16,63,87,48,87,58,97,84,81,57,3,64,64,53,61,12,25,100,47,61,34,8,48,46,13,20,76,39,94,76,10,1,5,16,95,31,22,16,29,67,91,75,26,14,49,47,42,72,28,27,28,29,70,14,93,59,97,49,19,37,90,85,83,38,42,70,4,8,64,45,38,53,29,7,12,29,39,32,83,30,39,29,40,51,64,70,82,38,97,52,13,54,2,56,76,93,27,83,92,35,100,56,99,13,95,97,15,91,14,34,12,43,94,84,97,95,29,52,79,71,5,46,40,9,6,54,38,95,45,50,1,52,7,33,25,44,30,66,65,47,28,51,73,94,6,75,90,86,79,32,72,34,58,73,91,14,47,46,91,55,30,51,46,24,71,81,34,100,17,16,9,53,71,18,79,31,42,87,87,7,16,7,10,28,47,43,42,17,76,12,13,25,24,10,4,2,95,3,40,51,40,66,60,82,46,44,93,10,58,22,80,18,6,52,72,64,64,39,18,35,37,1,19,54,38,24,17,10,95,79,86,76,47,61,4,21,5,43,99,24,38,58,22,55,69,3,62,6,65,2,34,83,51,67,45,40,89,68,23,41,44,85,61,19,14,46,24,86,9,77,93,36,43,53,20,79,67,76,89,43,35,62,82,77,56,88,24,29,36,6,37,26,24,89,75,65,42,66,12,33,21,85,84,66,79,31,26,81,38,88,64,37,41,17,6,58,54,15,95,33,86,43,39,1,17,84,62,68,38,80,88,59,57,63,43,42,13,10,69,89,5,2,67,82,27,19,62,60,72,85,2,50,26,66,62,46,38,5,97,74,42,16,1,59,45,92,10,57,14,76,67,83,29,94,10,29,45,74,55,73,3,17,53,38,65,27,25,93,28,84,5,99,15,71,58,41,26,47,58,65,79,12,18,68,40,20,45,99,96,4,28,32,93,43,48,64,29,38,36,67,58,10,4,73,40,72,63,61,74,20,93,21,93,91,86,47,68,65,33,26,51,56,13,42,80,19,64,28,77,7,67,15,28,14,52,58,65,87,80,55,67,19,89,2,51,51,37,28,100,68,97,52,18,66,39,98,67,21,64,74,65,43,43,1,26,84,84,53,74,20,46,92,17,37,85,41,6,98,77,63,85,13,29,24,41,58,17,91,91,38,1,95,81,33,91,86,76,48,92,74,7,40,44,99,18,25,14,39,20,67,85,41,97,89,42,91,5,69,7,32,47,93,41,42,26,97,83,21,19,67,85,86,93,9,82,85,88,99,87,35,11,91,49,81,78,98,95,67,41,22,45,10,86,14,26,31,15,76,87,26,70,67,10,60,47,6,76,92,86,75,3,94,18,80,93,51,83,94,11,50,77,29,4,91,75,77,55,83,52,60,24,29,9,54,7,84,5,96,99,82,96,38,25,70,81,4,78,35,48,28,61,64,45,18,78,86,79,15,4,52,78,67,49,22,21,52,36,10,68,76,46,98,71,94,90,69,65,38,35,22,94,9,78,79,46,66,81,71,40,59,18,28,35,65,62,30,100,31,46,10,35,19,77,4,62,81,72,50,73,55,88,99,20,83,80,37,15,100,9,62,57,45,24,95,65,80,23,32,80];
T=[3881,13007,29095,4113,5075,14205,15634,1869,3225,24645,13039,2101,466,9160,7737,2776,53,2000,25431,4098,18344,133,43301,22987,14303,17187,5149,1490,32908,1727,1,32868,966,9845,9680,533,16697,35349,1643,1496,590,20105,46586,3567,5231,3036,16113,12552,464,31630,25220,3222,6001,1920,10588,12332,4875,23322,127,3082,3196,21,23224,3841,25130,2040,3201,3661,2123,2644,16814,14017,316,1466,11271,1841,29106,1874,1219,13269,18914,11728,24182,36444,1439,16857,1705,625,1121,5698,1,2692,12381,5866,26576,21554,20099,19734,7931,33467,4634,20842,452,885,26638,1906,62,1285,1144,6208,3154,3802,913,5307,1374,6565,37733,4788,468,14350,3026,2614,371,2576,7770,20608,389,61088,20374,2143,13064,4212,46112,1727,5334,1,8403,200,265,16391,2568,19394,13908,6716,188,8767,11247,2075,4588,6963,2504,5832,8610,7916,130,3803,11940,33335,7940,1810,20551,83,4287,36639,7346,307,1676,4402,975,464,191,11247,23039,35334,3949,23863,6787,894,25573,16691,6394,28075,126,1597,9871,2106,10515,1,20234,40523,15848,1963,1542,17195,3145,30548,2807,15489,1069,6476,12828,25285,300,14065,7438,745,3303,2383,3261,2150,1070,18088,246,28814,1948,494,15857,11963,16148,11285,2369,6564,5300,1992,11363,12466,172,1894,7805,448,1413,3489,11043,154,468,2712,9212,1084,9036,4298,3797,1823,4911,24259,10806,10663,9212,2429,8550,9292,17336,3106,21605,24197,96,13091,19737,309,4219,7471,5144,57745,9128,7862,2171,6045,146,3982,15330,919,3492,48271,15397,1277,5678,25958,3033,17526,1587,2382,4738,11473,1521,6035,147,40265,1610,2227,6062,2869,259,9286,11964,133,10654,46754,1625,4431,33735,4045,3532,2313,53,13045,17076,258,16357,1485,567,5501,34985,11796,1561,249,10731,21662,24113,1958,55053,438,1,3815,4059,4743,4813,587,9393,33115,1039,4339,28674,780,3796,1136,2394,6492,16037,2298,10125,6415,9918,1221,172,123,10777,140,1709,11292,197,6826,3598,6763,15786,4601,5891,10838,881,1999,10570,13240,36140,2374,21234,4204,23702,3232,873,24234,7086,7321,5005,10925,41593,1041,12719,2468,26282,1453,42620,1932,39247,10704,863,25645,893,21146,1,49201,14601,1049,29181,5634,1920,676,17255,3080,3709,192,2721,11998,4592,6283,11047,5383,5025,546,1928,559,4658,8044,3440,14516,16167,44,3051,63,1096,14264,4210,5998,23593,1139,2705,2366,9736,735,24970,2118,10265,12705,28677,42277,6273,12518,451,377,1287,13229,91,1514,1162,6869,19536,72,9876,4334,426,4028,2760,728,4597,24050,33336,44023,177,7150,32633,59,3096,26876,775,25271,4683,16224,1036,30622,43172,7401,47192,26194,11582,2123,9832,27857,10537,4997,51326,1950,3028,2955,2328,20432,89,44961,563,31603,2182,24914,1112,13099,352,1672,7546,633,22799,11877,5634,38096,412,4748,33,44,7120,108,6479,8133,318,18288,20144,46,415,2320,2541,3219,2285,41610,14158,1452,1778,197,2395,13347,3546,1081,32924,41118,3560,284,41160,505,4001,7303,348,4563,2053,8602,6392,2562,1872,11567,12948,2785,6346,30633,7633,9085,13214,8139,10967,535,15439,344,9762,29696,4744,263,1479,18547,13598,1962,4168,8888,7915,10314,13073,4201,1514,81,15121,14785,6133,12910,10799,986,4452,2699,7697,5294,37942,318,9968,889,9175,27750,31977,20660,4735,17117,10144,8596,46247,17188,5705,8682,402,1811,2091,3100,6732,5164,15193,928,22438,15753,5377,24363,487,442,2340,3171,14908,8146,18987,1789,5303,445,4595,2770,4980,1097,14624,10472,25522,2305,12476,39698,4089,23536,18178,9534,5659,6407,3390,586,32874,88,4251,1207,24851,8410,35188,4746,3606,2257,941,56177,5403,1154,9745,879,3448,3200,8168,4761,258,7079,1019,10815,9174,14378,10950,6910,11873,1113,1373,595,1298,37199,35347,1,290,122,2486,6402,384,15571,2830,17410,13,2845,3269,2315,6010,6258,487,36664,1626,30039,11761,5136,19370,1707,2469,10343,3857,5089,1105,1949,23949,8701,14906,1,5456,5959,9890,26036,6246,165,7791,26872,11626,9811,4988,4586,10345,4542,4688,627,13592,26059,599,409,332,14092,32499,2251,3007,289,2870,2428,32507,7049,9207,10120,17720,4967,3078,4741,49,3516,20572,17635,13815,2284,13355,23354,7470,1647,3107,30336,1866,506,739,4683,9819,3052,4173,15120,22884,552,26725,7886,3845,4362,1461,24842,11717,210,2322,4193,10604,9957,11913,54502,3441,11752,3101,32832,43,1393,57,357,1539,5489,2090,3974,31,10456,36,21635,3011,1497,10480,20373,27936,123,40021,8475,89,1029,16251,1229,4718,909,2003,3454,30739,1,3917,4456,48300,457,1021,5824,19591,17045,913,729,44,16081,642,239,15347,311,17665,21586,29857,32791,1573,7007,6285,307,1349,3470,14672,3965,19537,8317,1429,4902,1057,2893,2970,1314,24065,57065,15718,5588,13656,28500,8903,30075,473,31120,108,10787,1794,3817,1489,12718,310,22237,3730,2457,2891,166,3984,18340,6170,29987,30547,107,23054,475,47908,12298,28047,6788,10796,6851,4091,21928,737,974,14277,6668,21355,1590,25265,16112,1965,12087,4870,6255,17353,8884,3511,1635,2108,11588,1750,74,11894,7193,9328,4277,3789,20746,40,2597,32719,4792,39967,25855,7695,16657,1724,5231,541,643,18500,11722,1397,7048,1927,2824,8431,5360,52392,15640,470,4763,60582,28710,21445,9456,6977,5924,6785,13300,35084,1368,355,13214,540,1677,5130,9664,321,6629,14549,4675,4072,12744,38921,13443,16961,1999,23462,19145,37704,26583,27228,4042,15354,1387,274,290,12972,13181,2614,46,5668,3156,4682,1459,6493,2472,3705,208,17381,1637,60,1529,34476,5,1120,12377,1747,32628,16172,430,15626,726,425,5093,20510,153,29553,4004,12264,42575,7344,10146,11659,5951,41258,2554,577,41821,13670,2563,1483,1,34521,11981,2531,2957,7406,19679,10152,838,3316,52674,7533,6679,668,3963,5613,25,14783,825,30272,152,1015,4715,9955,495,1,4924,16701,36693,1219,17327,331,619,978,10244,167,13022,178,2059,6061,12107,22989,11,1736,413,2200,562,12868,1873,3095,2092,3891,22081,1190,1,6703,1089,13180,2529,2415,6277,17911,8258,337,13817,1341,918,28634,13991,24800,15482,3294,15776,12760,1396,25506,3861,12776,571,678,7880,9608,2924,4962,2547,33243,3590,5237,25308,9650,3455,17321,51961,7,11576,8879,14952,29053,1653,1891,24117,9129,167,831,26542,18218,6778,25421,8404,433,1,38876,338,5059,2414,14747,24678,7743,6325,17636,38,52320,7237,777,34296,7991,44,4102,3507,3966,1904,7186,9115,19259,33136,52326,19457,1218,862,43150,720,1919,3493,1556,14677,32,365,846,2792,11311,21464,9593,26549,1740,1401,1259,8240,1822,25632,4271,15159,21115,4117,431,16185,4632,10572,3380,1042,6858,14064,2477,191,18983,351,5659,202,10279,80,14541,14661,16321,9774,11124,11806,88,5497,19422,806,3814,3940,5990,18177,5672,19206,33500,5568,161,821,17113,415,33098,17393,5689,5901,8652,14999,470,15285,4851,1087,1683,13488,38394,8924,1367,4053,1,14027,3827,29912,62782,12725,5103,802,8531,231,27764,4410,541,6001,1051,2729,17,5042,299,20,12553,6371,18557,4378,4221,6760,875,439,8721,7977,521,1285,207,2587,605,47106,22291,668,6712,34424,2967,14289,14756,623,9,4659,20532,20273,11709,1422,34985,1780,10087,312,14263,95,3227,25050,6681,7812,378,6519,1874,38209,1389,7465,4337,1841,5659,958,15330,12750,424,3235,4111,4034,1417,28890,7658,1523,16027,669,7828,692,1,32458,332,37497,990,22018,5324,591,26960,6367,7200,5200,1244,11781,2668,6158,19474,1165,11914,4618,1144,14641,19341,3749,21610,1585,19620,16688,4723,7329,33764,42943,3838,34653,1015,11512,240,5015,100,198,39236,14320,4209,40588,62634,5035,26331,17658,1430,1355,5690,3569,23900,9891,2163,11578,33,194,13602,30921,23851,4266,2935,10869,3154,10632,33718,48,20015,20093,5228,51,53042,19996,11476,23827,28709,1,1838,28474,254,28,333,5997,5134,26126,40191,28620,3752,7774,7592,17742,1028,5599,7852,3737,7526,23372,11472,6750,18633,1417,815,285,5768,41127,22660,788,19744,1128,1373,8383,9729,20,6858,13937,21364,24509,60,12023,6074,1862,17718,1976,8033,15670,18821,37381,858,604,20981,4204,9648,493,3533,221,2654,1804,17617,4691,2346,1750,10992,4287,4722,4047,3468,27240,1050,1075,7094,7962,9092,821,618,4753,6261,435,2751,10734,35434,16817,6021,29315,5487,260,12394,5318,6280,2202,3637,24866,7712,829,349,9915,3017,35342,11531,5590,1958,9985,1205,7392,12389,8487,14808,536,20857,276,32329,4883,1930,997,13397,9362,182,3409,8145,7682,4677,1538,36888,3684,7443,36672,6093,5544,6911,2387,41947,7046,2248,5205,811,4833,15136,6511,8061,109,12017,18144,77,5290,1047,394,20470,5216,1778,2654,27484,3488,215,1,2091,1,2982,3824,875,72,2074,20960,4188,4532,2411,22609,10822,7175,20834,12660,521,5579,13922,27026,20441,13557,5754,5784,2309,7427,9657,11470,14123,2308,565,438,14596,62300,1491,9383,16644,27218,3541,19743,11430,936,56954,731,2540,4478,9657,2214,24252,10140,4120,2676,3232,31404,26646,1306,10031,17634,1991,54160,21718,2969,21143,2964,11747,1616,30890,6207,2349,66,7386,7111,11648,34063,3461,613,1753,2137,13971,227,49604,9964,10661,20792,5942,1211,4085,10417,5562,8577,2624,242,5154,8003,6104,269,2495,11294,7595,14311,4307,34272,3342,2648,21,14938,21302,5901,6900,32913,10048,1602,15374,25522,2177,5863,7174,3757,2739,17072,318,25754,1326,5846,4978,105,25103,23068,19141,3800,2800,197,2757,644,6213,1127,20170,2289,5140,2095,3204,57,60657,1715,2526,298,19728,30359,16089,4853,4168,2055,2867,15113,18566,342,430,2706,12451,5325,21832,2846,6037,1,22524,8390,7933,554,320,4833,22254,5013,4232,6390,5476,21342,13433,3993,25,4032,18728,12144,11302,3049,4726,8600,697,4418,3070,3086,12269,15092,9735,3718,17307,194,251,4325,19,2895,8550,1571,28748,476,37062,18584,5939,2174,1559,16715,864,5143,20693,1720,2303,10104,5442,29366,9295,3848,6386,27709,9801,1784,4342,4434,5326,559,14934,8277,9391,26786,6042,29210,200,19379,141,1575,1192,7918,5916,241,13951,16896,1698,13230,405,4717,1462,7010,645,7882,3338,1796,1123,19293,32883,2190,9780,430,5443,2105,18643,32669,56614,11234,644,10226,8775,2886,11986,2325,180,483,4193,9238,3879,18536,3247,6241,40208,43749,45897,775,1921,36868,8375,16877,2223,2742,6568,7308,2481,35297,3566,32213,6805,746,23255,15082,414,260,7820,25161,3030,7829,10389,12617,11736,202,248,3029,642,2145,3499,35,659,8328,13153,8425,11558,25895,9902,8468,60,3232,2186,485,1389,23237,2308,2801,2672,7563,808,3194,1392,19829,5115,2626,246,1088,2477,16454,7617,376,348,297,14642,9917,37521,71,1827,4411,13346,1012,7640,11194,19220,11679,7619,7039,46948,1,642,663,2921,279,4073,7719,123,25978,8353,740,332,9176,35612,3993,2258,546,9628,10679,748,275,1732,44888,13848,48507,5749,103,1360,3047,99,3709,14807,27367,3273,349,824,3270,5939,76,15977,18621,6904,4400,9621,17339,17315,13149,30856,2914,3723,9540,39354,8506,4007,3544,3074,4475,17218,4169,3774,2524,695,22319,13758,27504,24258,1692,6284,294,52,8539,36085,316,169,7451,14517,3593,373,22,7,24767,452,10826,25325,15185,4263,9912,99,7542,18388,1,3306,11686,8290,4962,1982,9495,12274,53,35972,6626,10388,26714,56744,29902,20666,2071,134,7826,124,8893,7713,9942,630,7647,4643,807,11083,8631,18905,927,10895,32572,1473,10348,34253,1,30,3857,7218,3325,29070,100,3505,601,1,980,2936,1082,1198,35260,1079,5772,3087,24309,9750,1612,1525,8608,1,7822,9153,14710,3913,22227,1934,13062,8776,54036,15796,2772,17154,1652,5072,14960,470,504,5461,2589,256,2612,864,26204,26883,38000,294,4187,2681,7020,5224,16492,34305,9229,1,12621,77,5133,3178,5643,3470,4900,742,1515,9547,817,477,9192,20344,1,1,3279,3543,982,538,6105,3505,2523,866,3120,22310,386,9243,7220,13751,15542,4075,4949,2430,24589,4131,14710,104,10294,10835,253,37235,16236,9824,563,9189,5448,6592,346,732,38211,8194,12196,9886,2048,1342,3980,8375,68,8300,3759,2292,4243,21268,20,3574,6327,10351,5955,5398,3026,49,3968,16832,3645,17791,2600,25349,773,6,306,855,6460,1792,6028,50788,25814,14419,7465,315,9961,9680,3537,7485,25815,30426,5310,2985,23326,3230,982,1101,11053,530,6123,463,1542,25571,31832,2424,14645,12900,19420,553,24085,2423,19842,243,1686,28731,9684,884,6064,54,1606,24180,2762,1942,36743,958,2590,8446,910,60695,2733,315,3324,1656,5062,585,6412,1259,20678,1406,1829,11525,2818,9274,2376,821,3362,5303,2850,11246,8161,5250,15824,11707,25344,31075,57,64,39081,15724,394,808,14659,51109,17694,19477,7737,5828,21941,1,7524,15325,8911,1695,14278,2016,13285,9359,3160,1571,3858,49498,5067,1174,4653,1159,1601,88,1114,9471,29269,4518,341,2122,1035,1624,255,3594,8325,1785,103,4174,1573,44,11795,16206,6081,127,1194,1409,11281,1006,12036,114,12672,32217,3042,2339,130,3784,10959,1026,19842,40354,340,2467,3723,489,7926,12125,1640,898,20018,27484,12739,163,2530,1478,793,1278,1739,11085,42994,31217,1009,1164,128,5002,2099,1,15944,4478,379,33980,547,1728,965,1592,26706,15639,10071,18792,843,10741,61,2415,8837,57736,4247,1959,1132,216,2266,6375,35387,1437,9396,211,4380,8029,5757,2738,283,2488,6145,4979,3862,1327,2519,3095,14503,1065,25674,3316,3212,20879,296,2156,5812,4982,8963,3533,2735,5662,42731,300,17424,1027,310,2050,10145,34693,1727,2881,2773,4006,14953,3832,37551,50015,1758,9773,4771,15,9147,285,1365,355,1308,26497,9330,4150,349,38271,23141,389,4319,1084,2139,31880,199,6571,3419,63,567,8778,5721,13617,644,809,2387,18504,44835,86,5602,6219,5048,27204,19524,1514,191,1729,8517,13209,16530,10682,5571,11319,416,798,18125,1939,634,9924,21734,28608,2374,11433,12979,27851,415,15567,21260,14003,276,531,23828,4765,21127,7468,18310,10370,84,561,18890,8444,18650,2888,6608,19310,36840,12369,199,8111,21920,85,20649,1450,2239,448,6469,6983,8139,13478,1366,19903,45486,866,155,14718,7456,26282,5446,3782,4921,1145,44556,13487,15164,6059,1317,3688,13802,9987,2431,5815,1319,6124,1941,1444,23285,15550,1787,5607,10633,178,6011,290,6181,3488,29011,13990,410,8466,18005,17455,3683,10279,3946,365,3140,19050,18115,4138,1,655,37218,3084,31647,259,13,14379,6656,6400,38533,151,2111,4343,5127,26713,3341,19836,8050,3770,82,2475,7376,3323,1638,7815,4203,1451,667,2684,17316,5406,2208,130,1011,190,11331,31767,1103,24704,27143,254,5752,13204,10563,2462,7681,29,15761,2757,19440,2027,4815,16319,1,555,18673,1659,11922,7136,6228,3283,15621,15080,10004,36824,773,13991,4073,1292,13035,13641,298,16739,10251,3683,5747,77,3810,329,2452,1251,10473,15201,276,3529,6943,499,4679,13447,1242,198,852,11276,187,1282,23499,45,2729,37322,25455,52762,10523,1250,1606,11265,3933,2318,1423,10474,26837,14574,36818,30260,19103,10936,135,1578,7879,4934,2772,26514,17240,629,13893,72022,12293,10306,28257,137,688,18167,1240,3770,3916,665,32780,90,576,876,7514,31581,12740,5658,15588,7084,4413,1209,15007,53,994,295,3011,20283,2793,373,20250,1130,447,8,34006,7955,23896,8144,1975,16629,957,11059,26972,25398,12420,798,5628,3386,29002,3683,26422,1926,20511,20797,4412,6415,1026,18230,15946,1794,48589,30815,3661,7823,1880,463,15731,13618,32565,18379,32274,5687,5648,17016,15700,9691,245,210,17057,3644,93,36105,18295,9165,10250,1774,159,12993,12460,1428,6533,6136,478,8109,83,5849,16300,102,2206,5046,1737,2480,1348,801,377,27361,14966,14055,10357,10454,28119,6507,25996,2300,11678,21377,907,5635,4517,497,3281,1970,32694,8346,37038,37639,6407,1420,1516,29530,645,8288,14402,17967,12926,14526,11934,37805,5273,1406,5556,93,14292,3985,1828,4768,2347,2355,8061,796,4631,6978,2567,1102,1171,1456,2287,6677,3054,10928,10280,6462,26569,25194,11072,5775,14781,4396,1510,3084,719,15242,7785,467,1061,6373,27019,11053,976,4742,7199,971,18146,9905,3115,9171,1397,4636,19555,15424,34455,9729,14211,10520,1168,855,9907,3696,12956,4583,927,1,14063,7605,9356,198,12285,2939,173,1430,289,38545,24109,300,1630,15496,11533,16165,37,9906,28973,2316,16036,33939,2697,1121,30087,1320,39328,33920,8233,10909,2212,13252,9111,1128,130,6722,3522,7804,49717,1626,5580,25221,17195,8798,5299,7836,6287,1519,38797,4680,18196,429,2782,712,27694,36065,5353,4930,22135,17852,21382,76,4948,14606,201,23702,6192,5740,454,801,3753,58,13427,22048,7970,7132,9025,577,34516,27766,39988,2578,11173,23724,1456,352,4341,31207,16968,5114,5390,12372,3913,6999,20434,8957,722,1855,2066,32320,22155,13432,3370,221,1922,331,15853,6570,15254,44618,1629,1609,164,11511,9524,20108,109,3646,4682,197,2356,2398,5256,793,9534,11877,363,2213,20328,1158,5696,5749,7796,40,1275,6954,32559,36603,2289,10732,5898,26264,4517,6067,19847,17215,371,4307,5036,18108,1703,1390,19398,19217,376,3222,20560,1,337,255,3783,2461,2394,29674,413,67088,2838,762,21660,23012,21202,8012,1960,1001,2309,1717,13648,3877,23996,716,56548,1242,81,2379,8353,40269,102,7197,10533,12132,9274,4464,17178,6075,4918,25349,1,22844,403,18311,17149,7103,1743,1,7305,1790,1567,248,10070,121,33735,7396,26128,6524,443,5073,279,18203,26192,3776,3569,2399,2486,25536,44724,954,7321,2910,31840,14320,1,18617,31998,4518,6199,9824,2192,3328,443,2001,27205,14612,819,9524,2436,1615,1218,2363,2183,8464,4144,16614,10097,13313,38053,3856,25853,333,152,1103,19595,25938,1028,4230,91,5934,488,11677,18702,493,3763,4624,1263,16553,12032,48094,7843,6841,7386,10003,2302,809,7446,7060,3694,28766,10916,1394,6294,32657,993,18173,562,10346,19162,13277,2588,5122,10306,1140,12699,28224,2708,56611,5009,22247,878,8643,778,3571,2266,966,23,607,5409,14495,8781,30910,5019,6931,4362,32413,15257,40008,22952,9029,4213,6186,1212,964,10736,46,2629,10233,970,1789,1,13906,297,3102,19312,379,23592,856,377,5941,1647,31239,4047,2145,13381,3473,2551,53681,5715,21955,41369,30553,13424,18801,114,29545,40193,8613,11366,1938,7221,28068,7620,976,28984,7886,2866,6895,24552,28773,322,3428,31568,9405,73,7806,415,1479,6060,311,44606,26419,506,1039,3178,6634,17803,1224,8592,2340,3179,1330,10803,230,3131,9634,6341,2290,3543,12201,19731,5018,2321,8810,13358,7010,1633,2430,4159,537,10233,3388,8152,12362,856,5256,1303,1658,8180,11846,2406,12470,67837,91,1546,9669,1,5245,531,40808,1965,790,2603,18071,6969,11403,14131,2285,3527,4284,49,9697,4153,476,5615,22508,1131,674,38664,275,666,3275,12701,243,8484,13131,27123,34394,13775,5998,19253,8364,4507,6316,1198,1184,37798,63191,175,2079,2691,160,4585,41,22986,29470,15507,50,5071,6043,6657,27199,25970,12121,18581,33256,44621,60,851,90,5815,14176,948,29338,1001,6911,6977,138,24294,30875,690,2983,6639,24535,1115,1198,3449,15134,903,65,801,5184,31206,33504,2330,6986,565,5477,1269,15158,937,44263,7665,28449,13575,2941,6135,8696,29927,20269,2766,836,3114,10554,753,1626,11890,9355,1995,13767,331,47676,4024,13887,13801,10075,8887,586,6106,147,4748,13206,3421,1495,15552,4618,7903,15116,327,4543,11218,2512,9869,35856,60,610,36242,2357,553,13194,14060,27250,21673,632,4711,564,3573,15538,6998,43154,10222,5616,15498,16918,1937,19403,1122,28,33380,286,798,23787,377,17055,2970,6098,11082,795,14601,8652,2592,3722,5346,6534,381,24980,91,41187,2939,10748,1387,35,5485,658,2001,5194,38093,889,20152,1736,1690,9726,712,47515,5910,418,359,27558,17250,1636,3279,8909,7299,17720,218,37151,698,8400,1464,79,3643,10747,11344,7632,1231,4543,2881,2830,11147,5104,2523,12421,1630,1,388,3350,26408,4209,914,28227,24,2645,8152,6352,3756,8169,2360,33995,5079,5527,340,26154,18333,1458,3469,1078,51101,32357,94,33156,834,9591,6260,9585,695,12661,31785,1456,8957,2485,3537,23089,52007,43,4157,302,13696,2784,609,275,8602,4832,27075,15650,3430,324,3725,12549,6738,9579,22002,7477,21510,55044,45778,1239,2873,25929,4235,3113,3253,3208,1060,858,1255,67,21,18519,23953,34,9721,9339,1222,3282,4863,33026,4647,47,12086,3780,17799,915,8006,2750,2044,16627,2513,1008,3141,7210,8129,12532,29866,4768,1835,3574,15871,407,56732,3806,30208,27653,7481,40499,1546,48179,17199,270,19439,3995,9797,1018,17858,20636,2841,26264,625,1118,12782,601,918,151,1,8167,4536,196,14666,1863,22382,145,13064,3527,6230,1757,15210,1352,79,9278,1376,5690,39944,2855,29963,10537,16313,5390,6748,17316,6345,351,7149,4186,1785,14810,1659,36,3638,10719,15555,3161,4347,855,10701,6939,8578,23909,6239,1514,43729,15438,13432,20525,5279,6662,92,28283,8051,7348,3931,6043,22700,4667,233,11042,1532,194,34803,914,905,26180,10622,14405,10748,62,1527,5038,18752,14494,3143,7224,5007,1840,627,15712,51,10080,8547,3,24953,15994,1876,3353,14408,10672,12970,20561,169,38047,8877,839,299,3939,3155,10783,7793,39,14287,15108,19163,2833,18259,8201,12126,11127,34762,65271,23055,9715,3304,28727,31335,3901,6740,21238,18315,1631,1282,4696,6809,64972,5391,4068,20774,5764,23680,13004,14653,40120,5122,4477,20041,3463,6918,1932,19353,5822,2476,23,13918,1530,11152,11587,4203,5037,12350,5775,10268,8473,1357,3719,4992,87,42264,3046,4994,11801,1972,12822,2847,21997,26483,1251,14,3612,576,10124,11919,5092,3690,6342,6863,1502,1414,25832,18706,17960,12634,5207,30003,136,11791,956,6511,5347,688,116,10355,3971,897,1947,17051,1442,9133,11,522,30787,6357,19018,18819,3773,20458,1642,6027,8442,194,18850,3484,1006,584,1969,43806,20069,9767,9052,18067,18512,5777,1405,6767,454,9041,15473,25368,3124,7269,228,10865,1,2421,13188,3619,1179,23242,4245,508,14237,446,1310,14039,3438,18861,6287,296,2943,6968,3028,8930,19635,6266,9562,2246,8780,12742,23621,63,231,14750,107,1816,35520,13236,7257,14185,2731,449,25985,44698,12240,9607,7659,5656,1172,789,2230,33067,3132,4709,2014,3427,2564,590,1287,13289,10679,14351,7952,10385,2612,25837,205,1931,85,340,3028,10355,76,10276,33020,1113,23120,1220,3559,1450,11056,16276,10632,5369,22627,3340,23858,1343,18773,9153,29781,7073,5320,544,11189,1589,1179,1594,1859,1162,222,52,5358,4840,2275,869,12346,45324,5612,5041,443,1569,173,5135,6951,563,9622,22552,1326,2900,30639,4897,17837,8653,1049,20973,19102,24171,27367,5137,1059,38989,39799,29480,83,2422,798,23775,584,11402,27558,8165,24409,372,17605,706,4580,4971,573,13349,18349,24158,1502,23253,11837,7862,22975,6669,41005,2735,10912,2749,716,5,7442,8347,15775,16164,17756,26735,598,4307,1323,4699,1242,1775,8744,8377,2010,34229,14559,721,1297,8684,24059,6201,5696,2811,1525,8477,1077,3912,11267,10072,2521,12943,5759,10995,59386,943,5646,103,11911,17262,474,1915,7675,22456,1746,3130,5139,9488,16416,127,11056,186,1615,2559,53,11687,2905,13305,804,36633,20209,4105,672,27098,56896,2956,742,1406,3219,21903,14240,2333,712,5669,1,441,1776,40487,8253,16782,6256,14496,1041,4166,38117,30371,18848,1,4524,53283,20473,9235,3425,41102,17230,2952,24855,1351,8116,14472,38172,2253,11456,717,9719,7364,35114,4537,441,63,11257,15025,4981,13712,20105,31204,2184,575,23,14561,4020,11304,2253,2368,8221,7939,9740,24066,39783,8088,2948,40622,1997,4594,476,1611,28689,1145,9656,113,10630,3119,7553,2830,1640,628,198,983,20326,425,716,7794,33382,5324,2603,4278,439,16393,1441,1007,17875,795,4901,7595,6349,1336,2466,5429,29023,26119,27770,316,13803,2174,2621,946,1127,1,5023,24210,3158,1005,11190,1892,43409,3415,1994,28914,30744,881,29613,1899,2938,7328,5674,993,4802,35099,3080,675,910,37534,743,731,11949,1220,512,16876,6475,17969,1826,10854,9985,5066,6259,1467,2143,1221,163,299,34348,33309,27114,12448,32555,23256,5635,1270,12144,3080,1195,16052,6186,8990,746,35942,933,6797,5812,7597,40038,14350,2106,39134,5051,7335,3820,11524,2970,17845,8745,13828,2436,2355,37882,12008,4986,50382,2256,1465,26726,1557,1497,42318,3894,14469,22518,1,6062,3074,15963,5559,8358,9452,1894,20315,1239,125,15534,1,383,9862,1331,2993,4588,11559,8297,3521,20538,3611,5739,116,279,4322,17775,17120,4566,29688,1786,307,9780,736,19178,12735,14884,528,1,599,4709,24743,234,665,771,5146,1347,6748,18431,77,18939,271,2667,679,25483,7138,2264,9541,17025,18539,2059,8099,42282,102,883,15996,6085,35223,5940,17459,70,18783,635,3428,1370,11315,234,29872,17384,18560,58,638,2054,22363,4083,9564,31074,2735,44970,3017,16859,2220,4791,19753,1622,18434,5656,44571,3405,8963,7141,3636,5857,19603,1791,30406,1511,18975,1272,1615,3207,14739,29060,35982,245,2455,6231,1,1045,7104,18354,12236,7884,17091,27629,7442,7065,5409,12552,6597,457,5586,4860,7174,7187,2928,78,200,847,624,15662,4671,10213,16635,2302,115,450,13348,40,27864,28558,2308,1094,277,5800,8520,4941,30253,11776,1285,3262,3266,12597,1102,27755,1909,1748,4718,17774,9721,7530,34409,45526,12767,4654,34800,16,8149,1177,103,16334,21732,12307,2374,13970,4762,2355,535,34508,763,46967,17179,483,528,1023,966,1465,410,44,8800,12108,13176,19914,267,2022,5878,2131,14807,5541,9663,19528,35013,34433,1787,2430,10867,13119,15192,17343,12190,2,73,2693,655,68,11439,178,27311,11913,6230,25156,2990,8577,252,9386,15976,43681,64254,4454,55145,3461,26691,32280,13539,118,9007,12954,40955,8266,24811,26300,40745,35225,6877,250,386,7629,216,7458,233,148,5893,50468,160,3631,2449,124,3355,349,22783,1725,14064,35066,23381,5648,15032,10366,11545,17757,25936,13480,1863,13243,6140,2776,3839,57025,12364,24470,1,7032,10255,62363,13849,8391,101,2908,4058,375,8838,393,4537,1809,6297,18498,1378,53,8850,7950,21358,4959,1905,1292,27558,2279,18510,391,29947,1036,578,11186,17964,35256,1289,34594,4067,29492,1044,16031,20654,11335,146,142,3165,1713,22662,31556,9617,1733,1,269,8645,2786,6893,1761,401,11608,23487,411,15064,31426,2344,2127,2059,5781,22,13925,554,239,10611,530,1707,144,978,4087,12755,20952,4367,946,22437,1508,5345,1539,13659,11872,1709,15295,7123,3496,367,14856,4327,2691,36190,5842,323,538,3317,1951,8603,5191,16268,4263,11273,498,18454,1294,19816,965,19032,11909,1492,43735,16469,3910,382,3778,2903,3346,1235,28101,187,17340,756,3716,567,1960,14131,1546,23547,614,364,11948,1460,485,152,3693,9127,1983,8471,13005,39286,13072,350,2990,3596,10266,66,15415,8035,9279,13531,8238,7563,3677,7427,13474,48373,7595,10897,6298,193,598,41647,6931,6954,2445,38918,1797,8717,2263,3478,3032,23118,4994,6370,2197,3371,22468,244,7769,348,49237,5929,3537,9301,18621,529,17476,5089,34510,17033,3126,4148,40976,9030,1996,1282,49378,2526,35743,19003,5296,220,1665,4279,4959,29346,20038,5599,9394,14210,396,10335,9398,6704,34566,10898,18848,7875,15415,4420,2255,12293,1,54,15131,754,11966,13453,1684,1013,47474,671,2860,9449,16764,6177,2827,9310,35826,3040,9566,619,4026,16505,22816,2358,17500,4269,20545,11749,30809,10792,3951,1817,5484,11905,32920,35,1422,4022,35326,7126,411,12889,2281,4222,18304,2468,1774,18746,27470,754,10210,577,34,1122,5691,115,16593,4901,2150,13896,134,3174,12596,2579,3753,281,8487,6700,2021,1255,1300,13729,5216,37,6305,4303,1036,7449,18140,1460,2170,4727,4153,811,1779,2819,30046,2418,24758,29330,20980,30987,1,1760,1010,2440,1840,6023,59750,4124,8633,1206,12001,143,1487,17608,7888,88,2775,5042,6526,7567,10561,96,280,3158,1906,290,9408,10034,470,2976,3806,22753,2102,878,130,3887,13367,6830,4839,2877,6561,7685,16597,1861,3530,1723,4668,2069,9775,21447,911,237];
A=[76,139,749,118,61,452,210,144,36,404,162,50,6,246,108,80,132,31,272,43,221,5,530,244,230,534,62,28,364,44,1,392,546,283,146,34,171,401,164,28,30,231,650,49,87,70,601,481,35,671,431,421,173,66,158,220,75,250,13,232,79,2,360,59,307,72,87,78,159,72,476,170,14,165,166,111,294,36,152,216,300,337,699,382,439,293,67,28,18,63,1,40,459,138,472,662,309,207,328,452,48,476,132,19,490,276,12,43,21,148,42,101,413,107,17,270,546,70,9,344,40,67,5,62,81,326,113,660,298,321,190,92,633,28,111,1,172,197,18,289,65,239,172,114,40,244,572,53,133,178,162,192,97,313,131,60,689,576,206,23,384,96,179,532,207,7,530,120,65,14,12,233,654,481,97,434,465,28,351,398,193,476,6,30,188,297,133,1,263,421,289,31,104,245,34,670,87,618,52,470,310,417,4,172,78,13,201,27,88,41,36,388,119,460,61,109,191,333,188,137,337,454,234,47,229,322,10,70,150,19,68,60,183,29,21,220,166,54,116,54,51,292,101,402,113,227,291,27,239,276,545,37,224,482,12,242,400,19,82,127,464,612,310,225,64,62,46,358,217,110,245,495,331,269,375,424,117,727,124,377,153,710,21,142,21,449,30,110,409,95,83,653,217,211,597,567,260,133,661,43,56,486,3,500,487,6,221,26,42,275,723,262,111,82,257,227,321,51,598,30,1,63,67,83,103,309,295,514,15,58,342,35,430,555,59,205,210,217,136,83,600,22,33,10,160,3,162,210,6,82,74,104,497,65,96,215,11,197,231,426,442,137,235,93,337,89,87,381,132,131,64,248,441,129,240,36,291,21,482,25,642,141,41,342,48,488,1,611,218,72,307,70,109,127,323,164,113,3,34,238,82,83,254,182,83,96,56,450,235,86,37,248,216,174,151,5,32,201,165,492,243,22,75,51,131,78,602,73,181,150,353,485,142,130,86,12,22,264,6,23,47,205,227,7,176,310,7,106,63,146,92,382,408,601,9,144,538,8,91,271,9,295,83,329,156,452,692,146,479,677,164,136,170,497,134,239,527,88,188,60,201,238,2,498,12,584,139,679,47,374,14,27,111,18,314,178,187,494,317,82,8,7,116,5,77,292,9,205,296,2,111,263,195,39,448,658,182,92,29,55,43,245,193,92,432,460,114,8,449,43,145,357,5,158,91,101,113,424,35,130,292,754,116,392,124,174,275,88,120,7,304,21,109,300,167,6,137,203,152,71,69,538,131,241,140,99,274,9,210,357,191,276,312,14,59,36,141,54,540,13,192,11,191,318,360,231,72,200,109,89,469,334,66,144,14,326,413,112,110,232,237,11,351,220,67,449,28,38,132,34,235,174,211,76,67,162,421,72,81,14,223,351,257,142,208,513,638,242,287,139,100,90,44,39,526,2,95,17,651,233,419,178,133,50,17,709,113,73,137,151,95,36,163,98,5,116,14,240,158,188,278,73,135,39,470,168,25,416,453,1,6,19,63,92,486,280,52,311,2,94,47,84,197,254,7,455,55,323,199,109,249,110,192,150,69,62,19,30,277,99,171,123,78,80,175,421,375,23,91,518,186,167,331,89,272,86,61,81,145,475,318,32,19,205,464,85,168,33,348,91,332,111,116,244,224,60,38,53,13,196,245,476,143,31,170,347,199,28,46,326,185,18,9,88,120,57,43,192,287,13,450,183,53,45,48,573,237,13,39,83,207,252,409,659,148,254,67,494,2,22,11,9,32,226,187,175,10,178,20,382,156,111,378,218,288,5,456,478,2,15,222,135,49,43,32,88,324,1,219,48,503,10,43,253,219,306,28,72,5,233,49,5,226,45,357,359,426,358,110,117,186,37,15,430,212,49,246,304,308,190,111,94,423,269,418,654,700,93,175,393,217,385,6,508,6,151,92,265,26,154,23,523,102,29,61,3,124,185,204,420,606,18,267,18,501,363,290,105,398,202,62,361,107,14,146,642,737,27,355,245,47,189,66,129,199,367,42,67,131,230,124,8,215,92,623,45,84,608,2,65,392,111,532,289,118,226,19,218,14,8,291,350,140,144,593,182,221,116,634,225,10,254,702,317,331,121,95,305,102,145,574,217,34,248,52,28,148,138,29,204,281,56,237,168,434,185,581,183,362,378,441,431,503,45,376,43,10,156,159,391,236,19,231,41,120,17,112,28,107,23,394,44,3,69,474,116,14,440,26,442,253,7,266,13,13,55,227,9,522,98,184,468,130,293,412,107,420,74,45,471,203,63,28,1,503,160,165,39,82,234,176,10,295,569,210,90,592,101,77,2,420,62,344,11,28,397,119,45,1,195,194,408,17,235,45,22,50,133,10,309,3,65,272,223,734,22,158,34,101,10,170,59,58,43,117,261,63,1,148,46,200,218,69,414,221,246,21,531,70,82,382,317,318,532,546,409,509,26,512,199,321,120,347,114,180,103,75,258,451,82,216,414,118,52,231,597,2,177,397,206,442,37,34,754,174,3,82,582,314,190,305,96,19,1,393,5,74,40,254,391,270,128,245,31,660,77,15,345,126,25,168,390,147,44,127,112,330,458,574,260,14,326,547,73,51,41,17,469,11,259,30,152,164,442,151,606,37,37,40,129,23,311,51,483,423,80,55,210,592,195,216,12,99,565,102,4,195,115,64,65,444,14,476,164,517,132,420,176,2,463,585,48,45,67,194,307,62,494,339,284,24,20,305,65,408,301,91,151,362,254,13,217,116,47,110,200,603,97,188,64,1,199,223,336,702,264,100,33,106,50,314,598,32,79,21,74,3,85,149,2,127,113,532,517,169,358,271,86,203,222,450,21,32,31,122,562,551,17,273,405,78,471,202,274,9,188,280,234,178,21,357,51,234,37,182,29,188,487,78,128,11,72,65,440,17,162,119,301,124,12,271,253,6,84,415,94,55,369,131,19,185,80,573,12,2,331,16,653,73,335,116,12,370,216,240,84,61,167,68,111,240,38,459,184,18,177,278,52,304,168,216,387,133,247,375,440,183,448,107,330,11,90,3,4,692,287,221,718,740,193,400,248,43,49,68,44,288,188,37,153,38,3,155,351,273,56,82,154,284,121,391,11,249,203,60,7,752,488,224,285,325,1,162,322,19,2,6,74,77,277,464,293,550,175,85,200,20,212,247,78,152,520,304,112,288,80,21,21,98,631,410,95,221,14,162,226,349,22,672,234,307,331,21,132,199,105,321,51,82,380,295,379,29,21,393,55,484,9,116,6,239,121,325,133,38,94,322,73,89,458,124,330,12,21,143,149,469,11,22,91,145,6,60,633,412,206,90,325,60,7,301,228,99,237,53,280,99,61,261,150,70,688,141,306,71,181,18,95,198,103,406,60,413,40,359,67,24,23,470,118,6,50,301,79,78,24,397,39,269,414,215,644,72,250,483,294,29,64,129,135,163,111,268,3,305,412,2,138,30,5,582,144,103,35,360,315,15,1,51,1,43,50,148,284,115,430,86,63,64,337,236,127,253,214,77,261,285,291,335,355,179,129,42,159,122,384,167,35,30,45,221,674,35,118,419,481,47,214,429,31,605,10,54,72,158,128,428,255,193,228,38,477,386,67,154,342,64,576,386,71,273,128,469,46,522,159,69,2,136,205,440,406,323,19,51,102,315,44,510,548,349,321,89,307,42,333,378,92,47,10,67,285,150,110,31,168,100,154,150,460,121,266,10,248,389,298,242,342,210,42,211,398,369,318,89,51,105,359,10,306,41,97,153,32,328,330,258,171,134,9,238,11,93,93,600,30,108,65,47,27,688,370,30,20,470,521,434,171,52,42,61,493,298,7,109,115,319,64,793,44,146,1,238,190,91,10,112,95,396,95,60,266,65,270,175,72,2,43,262,149,162,32,49,89,33,124,287,246,228,154,121,75,399,6,268,205,3,69,161,36,547,28,557,407,340,25,19,617,21,93,432,37,136,167,98,383,369,54,94,320,201,28,48,458,148,66,231,115,231,305,70,447,63,283,7,26,49,90,83,152,474,215,33,278,164,78,102,73,11,82,183,98,158,528,415,31,228,10,138,34,211,493,580,633,21,117,210,34,258,83,4,12,52,380,58,338,347,68,561,557,590,33,46,595,101,288,130,32,110,354,41,658,147,410,173,9,243,170,17,9,422,335,150,93,707,273,636,39,4,238,8,59,41,13,39,152,210,91,177,278,361,111,6,42,157,8,15,453,25,218,44,112,38,54,20,259,87,91,4,270,101,233,174,34,186,6,209,164,380,2,51,99,136,30,500,302,194,126,134,217,556,1,514,189,51,24,58,198,14,499,125,350,6,96,536,130,63,342,105,301,20,19,31,552,286,492,136,10,59,64,4,46,287,441,126,11,424,151,84,155,239,445,295,55,99,347,278,152,480,66,44,195,466,244,63,154,44,79,262,210,61,70,40,428,140,278,270,51,120,16,2,90,556,7,5,231,351,103,19,8,3,357,49,457,363,208,84,157,4,84,598,1,54,148,218,150,84,199,128,4,777,99,252,452,584,489,225,38,5,94,3,203,140,115,85,86,220,97,127,120,193,23,304,530,21,118,542,1,5,118,108,347,368,2,63,10,1,17,68,33,54,365,21,77,101,275,157,22,125,241,1,94,175,469,100,402,48,132,223,547,177,96,298,66,90,419,66,18,203,34,5,35,102,464,285,392,4,272,207,503,272,379,451,310,1,184,11,179,189,58,719,81,42,258,221,65,45,116,347,1,1,48,280,112,15,266,309,191,21,245,430,5,201,117,309,186,403,233,111,402,140,182,42,210,139,4,731,207,145,47,139,580,83,25,11,489,146,161,339,60,137,196,97,155,280,51,44,143,243,42,38,93,109,82,485,84,6,240,206,96,496,32,338,29,2,14,49,591,80,148,732,410,334,206,132,137,240,173,105,400,351,152,99,676,87,20,23,452,67,170,13,124,349,522,141,210,332,197,11,323,81,585,36,232,345,489,11,73,2,24,467,57,95,683,18,28,174,30,729,73,68,66,21,244,46,174,74,236,17,85,298,353,95,51,10,582,100,210,379,209,69,449,141,539,376,3,10,423,424,5,17,212,564,193,636,237,149,565,1,275,181,146,53,189,143,212,239,71,65,386,527,53,48,93,95,26,2,19,151,322,69,131,56,25,60,8,78,415,20,30,69,339,4,126,192,147,4,31,20,205,564,241,7,231,658,312,254,8,43,115,130,272,445,5,199,74,6,117,127,130,52,577,434,408,4,59,18,12,201,23,187,569,707,16,31,6,634,27,1,189,49,6,363,35,21,13,62,298,159,347,428,51,160,2,194,337,598,70,323,227,73,89,268,543,117,122,46,165,244,260,107,8,43,64,187,105,252,51,118,375,12,342,259,62,255,5,245,81,85,92,59,129,82,490,23,396,19,169,66,114,467,37,140,113,45,783,45,417,693,34,127,204,13,190,4,136,48,54,302,352,98,15,539,625,5,59,38,26,398,100,128,359,5,13,291,112,144,28,16,50,312,529,9,190,126,94,581,322,28,5,42,89,433,300,163,72,125,7,42,375,158,24,193,354,324,124,311,211,328,8,256,343,477,128,21,331,114,456,161,543,124,3,66,333,90,192,70,127,483,440,149,68,113,541,2,400,214,116,25,211,226,90,157,24,278,517,15,154,223,88,347,256,51,235,23,604,187,159,97,56,44,207,140,45,62,17,111,286,121,363,560,179,58,150,9,136,7,551,49,356,515,153,117,266,178,105,142,290,9,51,368,571,54,1,33,604,247,404,4,2,299,97,78,488,4,71,301,83,542,219,354,85,66,52,253,123,296,203,167,78,265,144,63,295,296,44,6,29,3,134,578,55,276,367,5,116,367,162,40,108,8,374,37,368,141,332,517,1,12,288,172,242,106,67,81,369,160,283,470,14,196,49,17,154,321,4,188,190,101,128,2,241,359,41,83,159,306,4,41,85,15,310,209,121,15,16,126,3,20,386,7,149,573,410,724,668,188,21,550,80,109,24,142,496,528,610,356,246,123,7,30,103,147,130,320,175,13,318,726,134,174,315,3,69,205,31,80,59,58,377,20,43,62,85,382,339,82,168,212,80,43,195,5,52,39,34,335,33,415,576,176,427,254,362,627,313,177,78,365,32,238,392,461,397,118,62,323,496,122,275,111,515,312,99,104,118,473,324,72,502,319,46,180,22,28,210,305,464,364,393,91,84,182,188,394,8,113,222,622,2,445,210,123,125,22,141,229,268,223,136,75,22,510,13,123,605,13,222,215,36,558,267,22,6,320,201,290,338,356,591,72,382,28,124,383,38,70,51,6,34,45,413,180,405,613,223,67,23,370,194,128,158,237,265,436,123,446,86,49,174,4,487,99,65,297,158,121,221,19,256,607,33,325,32,17,64,69,145,145,128,180,410,275,114,200,334,129,28,56,125,226,169,11,12,140,704,112,161,68,172,157,215,317,142,375,72,250,219,189,361,148,338,143,15,189,226,108,269,94,533,1,302,175,236,26,125,108,10,71,155,587,281,11,32,199,333,191,3,152,429,83,305,341,136,19,342,162,400,408,84,199,82,292,359,21,27,121,81,115,581,25,429,319,203,113,233,254,159,130,396,60,249,237,31,10,571,490,101,61,281,357,455,8,74,215,83,349,71,295,15,39,64,23,214,240,729,79,161,17,484,465,573,42,179,282,66,6,87,741,360,133,189,226,46,121,304,192,84,628,363,682,232,236,98,16,35,5,178,234,467,552,22,87,10,194,341,425,18,145,143,130,64,212,136,101,349,175,5,26,242,285,248,61,107,534,204,102,359,533,138,212,81,375,125,155,312,383,7,129,65,388,270,35,274,472,6,76,288,1,5,16,54,98,67,380,56,699,43,72,493,571,216,292,35,172,94,72,296,90,368,16,698,49,14,80,133,676,61,97,130,420,96,78,323,107,78,278,1,502,17,395,204,123,185,1,179,88,150,725,174,555,436,232,294,83,67,77,13,315,494,490,84,34,49,282,601,13,84,37,392,240,1,383,427,655,501,133,26,79,87,140,563,235,13,116,80,327,57,131,276,367,74,203,279,585,418,52,327,6,3,20,593,392,28,67,2,92,55,124,287,10,86,50,174,287,194,490,127,91,144,174,100,144,78,90,39,439,140,28,366,416,494,295,11,643,235,199,220,366,117,134,187,598,145,761,335,293,15,339,14,209,82,24,42,30,137,150,216,466,411,99,169,527,452,454,403,225,164,105,27,38,315,18,71,570,12,96,1,482,23,34,283,8,289,57,13,370,54,352,49,52,227,45,32,546,189,358,464,520,156,483,4,302,581,115,364,62,212,588,106,31,406,434,31,76,456,499,31,190,387,158,3,109,54,23,296,46,491,417,109,23,57,272,222,53,91,63,33,24,170,447,35,144,148,345,100,230,609,76,96,454,434,130,23,35,301,14,187,123,196,134,14,54,253,179,102,329,76,315,729,23,61,321,1,72,332,552,545,61,31,370,137,160,212,97,42,140,82,295,50,94,113,330,15,164,557,6,364,39,216,6,95,144,521,577,260,78,198,89,208,119,32,72,447,677,3,59,66,7,110,5,423,364,387,26,57,160,183,328,672,160,297,419,486,86,51,16,138,438,29,311,30,315,155,15,270,769,488,36,390,310,88,13,39,279,35,2,15,111,360,488,67,85,269,56,16,280,16,449,132,290,237,43,156,147,392,271,145,16,266,148,403,18,121,142,38,353,10,490,54,604,425,112,295,204,135,83,92,150,82,150,402,84,101,302,37,113,217,174,240,401,6,8,391,127,93,234,328,537,392,281,304,13,93,192,217,530,194,70,262,473,121,389,24,10,366,5,121,268,6,174,39,339,118,50,150,103,113,39,58,361,22,340,7,506,244,341,53,45,129,10,90,152,591,50,427,58,216,239,27,640,239,23,54,339,200,25,147,192,290,187,25,559,9,490,107,16,53,356,130,137,23,74,112,44,286,136,58,217,63,1,19,89,487,236,39,285,3,224,204,114,108,176,47,593,74,117,42,324,252,59,82,18,526,509,39,395,101,117,332,262,8,290,325,243,302,246,156,289,651,695,49,12,166,84,10,9,139,121,307,446,53,464,142,262,145,113,570,393,443,564,646,50,109,383,89,66,84,79,49,16,30,4,2,421,346,69,141,100,33,39,472,372,138,12,264,46,231,74,361,34,290,233,55,12,326,96,113,475,343,157,29,182,223,22,744,49,719,459,384,445,43,503,447,6,634,63,235,311,240,272,47,278,11,16,316,48,33,72,1,83,61,11,260,20,307,54,231,50,83,30,646,66,70,182,88,301,426,55,347,421,183,483,146,597,168,24,132,99,26,207,46,4,224,118,307,129,73,73,214,132,92,480,120,17,470,437,199,641,102,296,11,519,98,247,48,361,251,473,8,237,46,3,554,52,280,318,341,219,314,3,124,109,393,210,100,157,132,456,95,192,2,183,128,4,356,234,33,184,252,108,493,347,9,561,560,19,7,502,80,114,107,9,234,464,235,377,519,95,184,189,597,679,239,147,98,436,374,44,115,360,369,133,59,130,218,680,305,51,449,92,538,713,159,601,83,497,233,104,83,127,282,645,26,3,685,62,134,169,82,255,125,392,132,270,43,327,74,2,571,77,139,205,73,204,43,254,267,37,3,124,42,329,138,98,77,238,81,55,67,310,285,464,440,251,424,53,257,48,164,71,11,7,124,56,30,111,219,25,224,6,8,345,141,234,225,44,231,45,411,273,15,225,94,65,29,383,446,250,221,229,315,384,129,30,93,214,136,249,287,39,78,12,114,1,188,140,281,18,336,564,13,192,73,60,377,430,209,137,8,34,86,48,114,253,69,130,37,147,171,272,2,4,351,8,283,470,211,75,157,115,21,372,548,125,189,80,192,24,32,456,366,49,99,108,54,467,41,30,172,634,159,196,207,34,266,15,58,6,5,49,121,3,133,448,62,517,192,38,212,360,166,108,55,377,66,532,44,359,218,536,132,102,31,310,200,37,32,34,19,12,2,95,255,58,52,208,511,88,348,89,111,109,161,83,9,178,269,109,406,349,279,337,124,167,304,247,334,704,75,70,707,435,299,10,107,21,239,21,227,472,162,472,19,201,14,253,125,11,271,296,292,65,247,122,264,263,91,610,113,298,499,11,5,112,115,216,260,234,415,53,66,26,114,164,528,311,214,145,388,249,45,88,196,249,63,136,42,544,291,374,62,239,119,50,141,291,157,697,13,86,376,232,306,12,756,277,232,82,79,55,124,514,32,324,21,95,36,6,315,120,174,11,520,554,91,20,307,605,32,196,219,121,403,317,26,35,97,1,59,142,452,110,205,129,266,12,528,528,492,200,1,155,613,515,151,221,484,217,247,304,58,131,212,395,113,195,22,504,311,479,67,480,2,222,309,84,280,221,381,61,31,2,215,373,169,33,141,437,176,104,354,515,169,141,465,25,544,342,57,400,29,483,8,717,43,78,448,28,14,4,23,338,14,189,278,404,398,59,92,8,265,18,197,208,9,87,90,79,42,39,61,506,466,689,8,367,128,167,29,14,1,125,436,73,14,249,75,695,200,133,313,323,11,320,79,31,222,265,63,55,375,284,249,14,690,9,12,122,15,18,246,149,213,246,336,228,96,156,115,106,59,6,82,413,375,484,163,376,320,74,39,127,45,67,440,271,151,16,559,13,95,64,311,602,403,113,407,94,200,264,180,40,501,213,398,134,37,445,158,86,566,393,186,284,26,27,701,140,157,576,1,134,32,235,69,88,465,34,279,245,3,208,1,5,193,46,61,57,163,217,113,237,187,161,7,12,95,325,465,69,497,39,162,138,10,281,321,407,205,1,168,192,355,74,43,148,74,31,523,247,2,758,176,35,11,346,134,24,101,172,207,155,147,552,6,14,381,112,634,84,296,8,209,43,64,91,138,11,346,229,520,93,55,102,341,349,178,390,43,605,104,295,57,112,343,57,330,83,491,37,129,459,42,146,213,21,351,165,286,163,204,102,180,542,417,11,27,268,1,51,558,371,171,291,264,310,203,152,85,210,130,275,113,160,80,156,53,58,111,15,70,239,52,149,388,64,5,28,591,34,295,415,109,16,15,159,297,310,455,436,65,34,181,529,183,539,199,173,57,244,405,90,559,658,260,54,354,2,94,27,3,198,619,162,58,253,75,149,67,469,31,503,173,96,23,68,21,696,8,2,296,240,137,313,4,120,472,55,373,240,240,504,666,359,24,36,185,146,210,641,357,149,15,31,17,5,280,3,352,490,180,364,306,92,10,147,219,470,716,253,575,44,299,341,166,48,389,211,476,264,300,323,458,479,91,6,178,505,4,719,12,41,214,629,12,39,28,73,68,31,403,54,530,355,499,179,157,527,471,238,317,319,119,173,107,57,82,747,183,276,1,146,105,638,196,335,20,64,68,10,290,225,71,169,82,263,18,2,287,173,299,213,26,73,292,149,190,34,514,111,131,401,440,390,19,458,476,614,161,164,694,115,35,268,98,66,373,718,215,134,1,13,192,98,251,36,248,427,492,12,182,393,25,40,31,91,2,243,33,4,247,12,420,10,16,434,185,402,84,350,258,93,274,57,149,573,58,177,200,128,7,254,416,153,399,166,94,9,46,189,118,100,171,313,147,76,307,81,229,45,232,149,50,536,301,112,7,74,44,205,16,366,15,260,204,57,86,59,146,239,473,106,74,530,206,6,132,679,96,59,125,355,556,157,42,138,61,138,3,363,156,433,208,102,91,169,131,179,644,321,162,111,3,10,496,277,587,194,550,75,93,156,74,408,235,62,192,48,39,226,4,369,155,644,134,109,124,262,13,176,86,390,178,42,51,588,102,35,15,627,59,610,278,138,6,41,55,86,351,221,98,305,432,7,151,103,173,394,268,371,113,628,51,40,303,1,2,319,60,240,586,22,17,540,92,40,216,271,109,399,148,710,140,100,20,537,448,270,187,551,322,540,403,501,332,159,44,90,255,456,92,41,416,452,165,16,165,51,135,190,30,26,286,391,15,179,17,91,13,359,4,167,55,25,233,211,85,425,66,193,38,116,472,26,149,92,310,396,2,413,566,137,171,323,63,41,270,276,134,26,79,303,71,297,492,480,421,1,119,14,40,382,105,667,128,293,34,122,23,92,463,156,20,173,482,119,120,115,157,4,81,42,201,158,149,53,35,100,357,35,53,3,354,498,176,96,42,82,91,188,57,92,33,266,86,109,342,355,5];
B=[285,148,775,231,306,553,640,157,95,418,467,100,9,337,199,321,177,51,295,79,256,126,630,643,492,602,178,340,519,221,7,535,708,302,406,614,689,743,430,50,42,412,799,410,353,256,621,562,82,698,543,637,198,512,202,388,194,625,97,500,710,182,703,96,546,149,361,794,185,214,528,431,179,306,296,137,516,226,687,287,567,342,763,732,707,418,169,207,715,118,46,566,497,355,591,781,406,465,681,643,87,707,544,796,726,283,97,791,36,401,115,218,501,232,102,644,734,356,17,781,390,327,773,269,250,438,304,683,605,570,483,135,717,537,497,473,624,287,336,303,130,773,291,746,725,485,648,259,527,202,502,240,490,559,200,200,776,661,304,281,460,419,428,704,532,11,596,235,587,22,17,348,722,616,591,502,650,132,757,684,680,742,229,410,455,783,205,499,273,580,375,42,206,268,103,732,557,697,183,730,319,651,6,464,576,21,333,56,470,69,406,645,293,727,67,123,704,611,303,334,743,602,455,94,578,432,37,128,406,682,478,349,393,38,404,375,486,425,153,514,126,431,228,449,171,598,418,167,400,666,716,494,585,647,89,256,566,503,164,212,651,616,561,531,68,175,486,587,303,461,349,581,387,308,486,777,161,750,197,488,524,732,49,294,55,454,186,159,456,279,95,695,247,653,682,658,659,167,682,91,509,638,718,765,523,32,414,51,555,797,780,268,596,96,710,548,362,270,742,67,2,402,71,111,148,404,401,546,29,156,490,117,586,589,454,450,450,360,747,139,707,310,355,400,161,59,220,438,13,239,200,239,619,526,368,599,486,508,236,573,658,503,238,303,362,182,125,394,341,310,170,431,587,200,367,177,454,61,748,248,738,214,178,504,517,543,624,792,407,106,716,470,174,167,613,229,405,95,740,265,118,717,553,282,380,571,112,622,270,108,178,474,695,603,773,90,97,272,728,510,520,128,275,54,411,89,690,354,442,182,502,572,176,254,143,15,297,357,81,361,48,585,374,556,773,683,28,123,399,148,629,409,501,795,42,286,677,22,234,372,31,386,244,584,478,677,713,278,624,780,222,162,177,572,159,358,583,140,309,455,447,575,6,764,57,639,515,724,139,744,137,282,220,470,645,414,432,629,553,133,56,434,461,34,699,346,169,349,778,31,151,779,255,204,476,798,556,183,74,182,75,363,773,701,776,608,140,621,506,290,794,496,28,575,174,427,492,765,360,637,734,776,214,564,153,181,383,157,389,23,395,29,166,344,294,14,264,463,280,241,305,595,342,401,615,125,624,161,239,654,264,294,583,17,71,40,163,747,548,30,394,16,374,637,721,572,708,581,736,122,484,641,79,301,110,724,438,148,503,733,478,783,670,304,351,505,30,50,172,64,288,197,701,248,485,266,652,92,216,88,288,368,624,269,457,796,668,383,638,445,121,272,60,98,731,5,586,125,680,793,524,690,781,105,98,750,207,316,149,541,131,404,639,610,11,395,43,769,270,642,709,84,190,497,709,631,52,435,476,4,127,370,352,105,639,576,166,635,12,183,212,443,202,599,9,458,308,555,705,269,493,637,400,725,77,548,86,81,384,165,217,329,747,119,317,436,454,51,304,667,552,389,557,146,344,627,261,85,191,619,410,483,107,332,526,178,759,36,478,637,398,612,328,769,543,125,73,345,43,582,609,478,144,45,252,743,739,407,65,725,187,37,670,657,128,441,98,341,594,15,501,540,459,229,57,692,263,150,47,552,251,471,753,709,151,445,119,722,5,81,13,112,391,443,444,567,11,517,274,414,588,497,622,433,696,54,567,600,6,426,363,188,538,162,67,198,395,4,395,124,797,36,84,738,542,517,67,157,7,247,390,19,263,221,462,573,774,679,203,148,799,322,470,678,369,394,416,489,716,299,255,534,724,650,606,678,798,451,479,544,545,404,305,665,179,590,153,392,47,187,112,788,213,190,79,18,785,336,364,652,719,153,518,192,636,445,451,193,697,553,400,777,735,87,800,746,797,166,701,779,51,225,114,221,353,614,391,115,162,774,656,101,564,350,773,703,233,758,497,142,656,334,663,395,185,417,512,577,41,11,553,730,514,390,785,402,459,438,781,437,41,578,723,755,552,419,709,725,203,474,715,593,282,512,81,633,473,252,126,433,285,431,685,263,701,209,615,601,425,444,711,508,565,62,684,759,15,567,604,468,723,25,253,407,357,32,591,143,323,47,785,125,14,92,543,536,43,531,770,583,675,796,660,17,65,141,296,29,598,134,186,595,132,674,516,377,467,546,527,707,289,171,46,223,716,189,621,109,722,573,272,50,731,710,546,786,657,387,99,431,434,586,555,19,121,584,189,91,254,206,220,773,157,377,75,288,459,269,31,315,129,610,440,671,754,245,455,499,196,18,767,119,697,138,127,331,103,15,265,76,216,752,592,657,269,734,143,589,244,705,541,538,595,650,737,428,711,32,563,790,550,613,768,242,350,121,334,259,705,137,762,705,227,728,722,783,6,369,425,731,654,730,91,793,456,92,190,644,364,227,623,359,557,6,431,670,350,93,397,487,460,295,315,191,717,251,26,370,517,276,192,479,231,470,229,412,343,703,596,794,333,409,676,547,237,618,35,772,15,564,69,532,205,631,172,682,688,53,103,282,382,757,160,699,626,533,350,475,611,245,307,26,213,593,210,129,787,174,169,148,689,614,585,413,546,353,429,282,6,726,775,691,449,229,679,518,160,672,605,707,96,71,668,303,570,557,151,384,405,444,19,219,223,53,451,257,779,755,738,103,2,298,286,402,751,469,176,78,152,509,494,755,70,149,573,342,223,687,162,164,750,202,751,729,347,610,448,148,704,715,494,426,316,364,171,633,784,114,639,737,138,629,502,395,39,402,396,291,292,203,733,158,250,118,227,34,395,489,737,453,156,140,394,522,272,426,353,365,567,17,299,270,11,138,569,125,125,602,244,622,411,364,774,15,319,631,28,740,92,687,345,42,424,468,433,638,346,460,377,393,791,222,541,316,35,622,408,794,660,255,222,513,149,524,436,784,423,630,243,519,477,354,6,311,751,296,581,790,791,617,458,455,49,90,103,125,800,225,69,370,302,523,451,723,571,102,400,273,490,404,797,109,782,528,65,18,770,732,729,602,498,11,625,509,35,4,13,194,180,648,648,689,680,228,384,624,29,277,416,81,716,523,480,320,706,445,55,33,555,754,625,150,736,697,426,377,782,585,717,244,673,391,384,183,209,135,430,103,124,414,439,716,37,34,395,106,507,242,436,59,654,233,541,679,56,283,776,711,393,789,392,451,27,166,360,209,537,73,63,156,344,97,453,695,444,583,782,431,268,16,411,453,419,277,56,561,542,613,285,457,103,725,192,587,88,411,415,101,207,509,484,327,465,148,468,86,132,315,539,325,624,81,559,104,555,585,406,198,618,436,218,649,118,259,584,574,163,245,306,224,174,150,419,358,488,485,70,561,578,6,605,452,126,66,564,591,93,154,95,72,77,109,577,659,367,631,225,596,155,799,278,308,541,218,119,284,669,394,520,647,275,139,100,465,208,398,218,203,34,493,361,689,246,379,420,642,331,453,671,92,773,291,360,89,161,280,610,419,479,299,49,705,598,93,187,368,185,743,387,109,482,212,614,706,625,260,160,91,732,577,583,476,728,242,108,236,561,334,530,720,582,416,93,678,133,420,487,603,169,49,150,351,656,541,150,284,378,279,543,760,123,448,13,268,410,348,502,790,517,357,285,459,615,458,160,90,241,727,130,392,78,151,448,381,408,527,284,280,168,29,792,67,455,114,631,95,549,656,590,107,762,464,42,184,572,692,670,216,343,52,82,755,325,100,141,481,383,716,795,135,277,3,467,505,385,228,478,129,647,224,551,651,67,288,253,205,63,67,687,427,398,365,153,137,171,339,598,699,230,745,725,142,424,701,739,755,104,724,692,42,776,35,637,528,727,495,29,788,24,174,486,157,313,208,391,791,680,462,96,339,427,40,82,602,726,394,421,711,584,577,450,725,235,599,695,34,243,456,130,247,476,271,54,531,502,182,708,297,352,147,207,186,544,593,562,353,502,26,536,77,236,507,749,670,27,300,348,596,556,257,29,25,61,551,162,612,394,640,793,575,609,238,549,658,348,530,331,43,424,519,70,705,191,525,354,271,311,322,20,456,472,391,346,114,796,293,768,182,444,377,85,194,786,56,41,558,401,290,239,420,362,592,85,716,642,773,133,544,243,347,494,578,393,120,601,422,593,539,8,321,228,317,364,97,467,769,691,627,470,7,242,134,178,274,653,452,418,312,551,640,573,3,563,639,618,202,488,220,540,744,154,531,17,198,610,407,414,640,421,490,243,53,756,604,415,517,653,38,75,461,391,711,436,781,726,143,754,265,437,324,318,645,754,320,415,603,690,381,589,542,195,242,534,304,261,214,325,466,295,797,165,131,63,590,170,767,651,56,779,69,3,361,701,14,284,363,376,226,113,141,303,575,145,470,566,445,97,585,201,527,649,13,87,383,363,791,142,257,169,64,795,330,519,576,676,541,344,472,183,237,19,354,265,191,315,410,233,629,525,239,762,141,660,786,55,352,565,4,10,342,386,749,409,114,212,25,23,41,110,85,596,789,44,581,473,288,180,160,370,448,24,172,196,684,206,538,171,347,332,765,204,155,643,121,287,452,71,504,378,784,53,168,210,744,366,506,8,295,335,620,493,581,531,517,6,387,609,562,296,69,726,114,54,288,462,88,235,121,795,2,99,269,792,177,32,340,671,272,50,522,716,8,236,322,419,586,404,240,420,606,225,416,329,505,424,21,764,221,184,93,774,626,113,60,13,674,430,344,418,300,162,416,240,477,286,190,48,303,343,237,46,226,270,146,584,795,185,520,210,449,548,34,780,93,88,50,58,638,524,313,786,550,432,650,246,185,348,599,107,482,606,251,645,722,105,591,92,734,186,515,81,269,444,715,228,269,722,363,12,375,159,654,543,273,464,575,38,82,567,78,779,160,206,789,565,42,532,82,782,600,596,221,432,259,429,576,745,283,187,737,688,460,126,236,129,701,290,661,427,344,428,769,446,780,574,231,228,476,709,8,36,359,609,711,750,440,343,675,11,369,257,262,178,595,567,583,790,400,274,559,627,380,403,685,190,363,130,106,496,462,381,132,577,47,397,73,112,459,23,152,189,389,21,723,353,290,537,37,130,351,782,339,11,776,710,739,487,48,171,418,373,309,638,10,218,103,8,287,145,234,62,778,682,577,692,128,136,44,673,54,763,784,762,37,600,615,637,376,257,357,74,123,670,201,40,216,96,396,258,672,673,560,222,19,572,372,747,180,507,637,106,596,594,761,466,431,349,399,302,501,384,146,562,461,425,149,689,88,198,471,63,595,627,75,385,166,465,162,101,235,785,617,674,738,119,566,414,239,492,679,506,176,485,763,201,792,99,629,742,57,347,538,336,762,272,200,699,218,605,488,404,57,720,734,154,799,636,526,544,300,129,638,7,362,371,244,206,633,46,93,388,769,167,522,138,203,611,480,344,36,160,276,606,397,288,187,209,69,117,471,425,283,405,361,391,186,374,738,772,9,648,574,669,562,205,337,327,472,190,792,178,154,302,394,258,354,370,441,547,512,182,453,127,672,182,437,353,134,32,426,259,133,364,47,292,717,57,207,707,115,686,397,300,272,733,660,617,273,191,171,515,412,672,244,95,34,210,365,345,541,743,293,224,170,27,682,27,676,237,548,530,243,453,384,597,533,335,321,268,94,719,793,345,2,302,651,741,496,114,47,725,302,92,768,24,384,311,682,620,350,376,385,292,259,569,137,672,790,183,288,534,673,211,318,527,656,121,272,557,527,757,244,495,440,9,143,521,232,56,291,32,396,403,629,229,661,547,357,23,309,310,477,507,280,127,391,184,561,500,55,331,78,150,492,629,32,687,206,102,140,15,276,365,52,362,693,309,23,211,369,334,472,616,155,363,32,159,424,749,490,162,257,652,524,765,716,778,55,578,199,362,28,328,728,794,624,430,510,382,36,63,237,204,220,348,366,14,322,755,373,230,494,25,102,336,299,247,260,423,451,40,358,134,656,540,557,325,235,521,139,62,532,220,96,398,40,787,38,417,689,194,484,693,580,747,769,203,160,573,54,554,476,690,653,272,552,626,700,227,526,126,640,447,164,304,721,477,389,177,534,785,701,446,797,60,713,486,730,431,749,110,658,344,190,642,322,659,736,749,5,749,478,178,235,31,178,594,557,563,497,709,64,716,109,124,722,31,325,365,528,775,509,56,48,451,559,322,615,666,777,158,697,38,384,488,724,147,469,147,465,61,470,408,747,731,564,537,32,514,654,184,529,269,363,546,300,476,335,131,195,415,587,520,153,555,306,189,635,42,590,616,46,523,140,629,107,349,288,204,582,608,486,343,130,524,797,259,319,58,596,268,454,167,21,386,724,212,305,653,624,158,301,528,362,453,229,261,653,202,662,374,742,308,38,231,466,589,329,536,793,116,649,747,433,170,193,468,497,220,375,642,303,683,70,306,632,239,119,758,658,554,329,353,183,98,387,219,742,454,129,509,278,473,433,357,57,305,654,237,736,347,586,460,425,177,524,542,394,324,725,422,710,358,62,309,654,799,685,659,504,487,599,58,219,283,213,785,460,370,29,629,107,314,379,765,791,214,688,793,664,774,661,287,451,664,491,356,100,744,788,241,225,706,384,383,572,355,648,644,387,773,283,549,301,118,245,707,288,420,575,602,351,174,21,473,654,531,76,190,221,137,92,307,194,457,372,298,18,103,466,308,400,119,387,734,671,265,380,724,691,684,513,678,295,168,335,405,16,413,332,514,500,95,321,715,21,241,526,15,61,105,272,197,489,780,680,709,55,149,654,756,491,541,56,363,394,586,712,283,486,260,752,116,94,611,291,740,160,103,171,681,165,631,474,150,92,392,7,503,403,483,250,334,676,3,258,122,165,780,181,632,657,278,410,238,96,85,31,748,709,680,451,157,93,369,623,107,468,541,800,627,30,525,694,746,698,335,400,159,92,173,800,428,18,417,185,584,144,344,773,652,106,598,700,699,512,147,553,8,37,303,672,514,406,356,215,701,93,459,609,47,461,185,177,431,401,578,235,185,324,536,281,401,644,242,247,545,640,731,732,528,729,622,36,655,601,349,257,540,193,516,220,793,226,787,476,419,30,772,112,795,106,116,76,489,161,721,223,541,640,350,684,539,740,765,575,392,285,109,72,505,433,372,735,781,775,186,3,758,407,73,415,360,317,173,123,405,609,406,673,683,301,60,128,567,228,772,501,540,202,681,11,424,678,482,445,169,234,616,336,37,524,567,34,140,465,502,76,410,700,284,9,318,286,304,393,451,770,469,274,280,549,409,239,378,237,352,163,171,209,560,368,342,357,478,196,349,627,212,129,780,496,195,661,443,324,18,745,259,297,695,21,298,415,303,458,394,446,782,790,754,512,381,243,330,395,764,680,414,91,680,516,598,268,234,78,589,98,507,557,131,137,371,321,372,606,43,465,64,252,17,243,154,705,795,427,122,671,673,354,158,36,145,692,740,54,716,163,66,618,52,614,798,607,236,60,502,603,763,755,309,532,427,552,342,78,46,247,539,50,389,264,386,193,25,388,792,621,243,532,736,149,108,246,348,196,12,54,620,461,597,698,87,411,72,66,457,108,540,280,538,246,506,208,151,728,522,557,346,305,199,595,184,201,500,589,390,31,574,111,764,534,338,538,789,163,666,103,374,303,416,548,757,484,742,106,692,778,444,347,668,165,735,598,285,557,419,796,621,518,506,368,14,138,244,309,616,702,492,314,797,151,442,31,247,723,89,336,366,282,366,157,658,691,228,561,468,198,51,246,467,124,493,10,667,701,462,79,734,253,205,202,581,688,200,473,492,436,457,33,662,283,372,269,407,222,35,298,324,581,489,40,666,24,741,337,51,89,594,348,336,73,513,402,314,344,361,209,228,522,2,329,341,619,476,52,359,6,673,384,233,380,330,457,668,170,370,442,484,650,342,229,47,730,723,366,584,112,399,393,386,70,708,481,314,474,348,259,476,652,797,738,181,524,206,45,374,630,231,435,478,409,582,571,794,269,172,609,593,550,639,717,382,258,711,394,143,643,255,84,346,98,134,204,757,447,358,181,519,86,173,614,529,203,360,408,49,289,581,428,95,709,388,136,101,407,385,281,569,773,292,89,537,277,763,754,387,765,656,578,558,121,703,746,13,665,334,590,407,316,662,50,375,121,26,621,97,118,73,80,178,311,102,570,104,556,107,683,218,87,329,729,352,291,430,738,723,691,96,721,566,564,580,272,610,247,44,217,160,110,327,78,246,327,325,367,613,576,605,249,355,607,548,371,21,539,645,237,721,235,425,25,740,284,752,750,762,307,698,124,371,598,41,628,73,355,695,602,717,605,4,167,305,478,703,541,706,219,646,264,787,5,377,510,94,512,299,349,708,353,519,730,640,68,764,638,447,143,532,125,512,567,14,759,635,297,600,576,242,352,514,656,790,395,606,191,451,385,45,155,785,437,173,197,246,347,711,505,199,740,97,692,762,497,800,609,755,277,689,232,714,516,774,742,7,736,252,266,744,178,457,742,574,175,313,155,332,101,438,737,352,430,235,214,485,114,258,747,399,34,262,119,607,178,592,277,735,421,700,343,589,306,780,441,273,656,196,491,647,302,450,12,77,667,202,81,251,384,593,471,186,154,707,167,299,710,265,459,294,714,609,65,232,380,673,408,677,530,346,557,778,508,455,523,493,99,751,640,450,687,354,213,13,126,11,360,251,489,477,437,623,65,265,108,297,515,463,455,749,9,41,418,477,280,641,157,643,75,171,370,530,3,9,472,553,290,560,792,162,691,241,185,764,579,423,305,333,565,26,605,769,432,61,697,461,707,773,378,263,616,663,493,541,663,90,740,265,307,146,294,157,257,181,307,658,364,602,425,105,252,586,277,396,222,504,169,686,488,425,744,621,776,363,132,380,288,295,46,135,40,97,9,288,287,269,492,324,730,188,763,195,144,487,379,194,59,203,769,276,700,424,456,505,551,520,627,602,388,715,774,72,754,761,759,90,267,35,388,476,617,512,474,590,285,611,630,309,465,23,717,698,710,730,263,655,746,792,717,772,236,722,622,291,11,136,205,640,504,288,648,98,97,268,126,420,640,343,526,540,410,330,117,279,206,517,393,382,358,770,330,688,99,524,655,610,453,409,162,735,178,159,533,800,417,16,762,476,242,241,417,81,281,672,168,682,39,723,83,7,701,445,475,12,759,653,121,304,653,688,79,448,441,790,537,713,735,383,251,3,131,428,704,132,614,381,431,73,606,560,663,411,2,461,643,518,172,327,552,450,756,472,101,273,260,649,209,612,137,517,746,658,294,662,86,265,420,653,659,442,423,109,216,7,220,644,371,40,245,483,497,110,777,715,253,661,475,486,622,617,81,681,82,645,111,763,506,85,585,667,149,592,239,520,17,395,282,420,789,101,728,94,304,26,240,739,648,561,322,741,101,56,247,781,646,733,268,493,697,559,106,315,13,196,731,77,350,611,108,730,648,773,535,467,188,731,85,243,549,700,719,174,742,442,303,318,784,69,77,561,18,297,587,264,793,402,738,256,241,353,136,162,553,92,84,417,692,523,628,706,504,226,284,283,383,130,504,461,335,31,703,68,341,157,661,638,555,416,488,303,656,480,723,64,638,529,506,491,591,716,460,284,634,448,440,317,194,61,776,238,390,684,14,243,169,400,222,234,633,488,667,396,140,422,11,367,758,99,76,60,599,250,667,372,430,162,25,356,394,736,660,142,546,244,393,259,14,616,355,450,404,106,605,610,459,107,121,481,275,220,756,654,63,793,759,41,640,635,232,35,245,229,241,465,167,578,701,56,573,437,770,93,569,23,352,596,116,167,201,13,613,393,637,430,92,567,633,479,284,443,183,639,142,497,351,344,367,375,797,409,531,66,490,757,105,717,644,23,684,305,319,730,459,660,375,702,422,22,140,499,267,497,564,470,228,408,284,400,253,195,219,234,371,454,198,260,534,338,54,95,357,19,754,559,484,518,564,631,755,153,737,209,711,493,177,72,244,651,478,477,533,545,242,285,470,550,566,556,344,303,77,578,465,378,560,726,661,57,725,62,585,80,73,220,774,172,568,288,164,621,774,549,391,729,246,470,46,245,633,711,14,671,516,669,144,726,148,328,520,372,647,363,578,607,800,371,587,227,447,232,503,702,464,163,43,582,43,54,422,213,753,609,265,580,556,233,184,243,323,661,780,317,720,202,782,583,271,406,530,225,748,491,310,347,584,538,173,48,233,696,5,744,582,443,254,682,117,197,430,614,88,33,469,596,570,469,626,717,290,727,596,690,423,787,126,542,131,149,438,751,194,556,4,511,242,795,365,535,60,131,407,198,478,502,236,404,433,792,48,33,478,254,302,278,230,291,757,180,550,108,646,351,170,648,650,561,56,515,744,726,429,176,743,669,287,529,174,318,704,776,491,269,21,373,267,129,316,111,384,523,757,138,303,503,52,55,80,234,55,563,692,5,533,48,613,282,185,762,310,597,243,400,589,479,309,405,431,689,64,469,745,413,461,390,446,694,404,782,340,167,230,613,158,470,564,408,442,511,790,318,232,518,788,481,125,677,384,183,502,219,293,709,276,671,430,567,781,410,98,170,725,324,652,174,97,663,559,251,213,789,551,760,549,409,568,776,58,347,596,634,555,586,359,471,459,301,443,201,505,346,668,469,383,287,4,168,669,351,610,219,702,110,169,685,501,755,248,510,226,62,354,377,6,584,200,792,606,796,542,614,243,398,118,454,186,135,244,730,191,43,65,673,65,722,655,729,13,154,406,120,404,572,215,749,458,356,572,248,250,786,516,391,565,743,192,790,568,251,74,698,408,375,732,31,68,694,186,359,656,303,158,413,315,731,480,224,315,604,654,414,292,676,357,653,669,655,473,394,660,425,411,637,492,129,448,694,268,21,638,771,670,723,94,541,318,575,257,282,132,191,42,680,641,184,82,312,664,370,116,709,423,278,54,242,552,671,199,149,531,587,22,424,648,152,579,529,169,348,303,557,297,28,187,385,590,539,594,662,608,4,550,59,66,462,335,751,297,495,45,249,520,387,720,302,55,424,703,704,318,373,279,16,212,471,745,603,219,481,136,368,498,73,456,31,494,543,479,158,135,319,245,753,309,166,65,283,668,522,467,459,310];